#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/stat.h>

#define SIZE 1024
#define NaB 257

typedef struct{
  int value;
  unsigned long prob;
  struct Node *left;
  struct Node *right;
  struct Node *next;
} Node;

int open_file(char *filename, char *mode, FILE **fp, int must_exist);

/*Functions used to do BW encoding.*/
void bw_c(char input[SIZE+1], int size, char output[SIZE+1], int *index);
void set_table(char table[][SIZE+1], char input[SIZE+1], int len);
void set_indices(int *indices);
void sort_table(char table[][SIZE+1], int start, int end, int indices[SIZE]);

/*move to front encoding*/
int mtfencode(unsigned char* dst, unsigned char* src, int length);

/*huffman encoding*/
void swap(Node a, Node b);
void sort(Node arr[], int beg, int end);
int huffencode(unsigned char* dst, unsigned char* src, int length);



int main(int argc, char **argv) {
  FILE *ifp, *ofp;
  char *input_file, *output_file;
  unsigned char buffer[SIZE+1], bw_str[SIZE+1], mtf_str[SIZE+1], huff_str[SIZE+1];
  int bw_index;
  size_t bytes_read;

  if (argc != 3) {
    printf("Usage: ./%s <input_file> <output_file>\n", argv[0]);
    exit(-1);
  }
  
  input_file = argv[1];
  output_file = argv[2];
  
  if (open_file(input_file, "r", &ifp, 1) == -1)
    exit(-1);
  
  if (open_file(output_file, "w", &ofp, 0) == -1)
    exit(-1);

  while (!feof(ifp)) {
    bytes_read = fread(buffer, 1, SIZE, ifp);
    
    if (bytes_read != SIZE) {
      if (ferror(ifp)) {
        printf("An error occurred while reading the input file.\n");
        clearerr(ifp);
        break;
      }
    }
    buffer[(int)bytes_read] = '\0';

	  /*Do BW encoding*/
	  bw_c(buffer, (int)bytes_read, bw_str, &bw_index);

	  /*Convert the bw output to move to front.*/
	  mtfencode(mtf_str, bw_str, (int)bytes_read);

	  /*do huffman encoding in the move to front output.*/
	  huffencode(huff_str, mtf_str, (int)bytes_read);


    fwrite(mtf_str, 1, bytes_read, ofp);
  }
  
  fclose(ifp);
  fclose(ofp);

  return 0;
}

/**
  Opens a file with the provided filename and checks for errors.
  \param filename - Name of the file to be opened.
  \param mode - Must be "w" for writing mode or "r" for reading mode.
  \param fp - File pointer to the file. This will be NULL when the function 
  returns if there was an error while opening the file.
  \param must_exist - Either 1 or 0. Pass 1 if the file must exist; 0
  otherwise. Note that output files don't have to exist prior the running of
  the program, but input files do.
  \return -1 if an error occurred, 0 otherwise.
*/
int open_file(char *filename, char *mode, FILE **fp, int must_exist)
{
  struct stat file_stat;
  int status;
  
  printf("Opening %s...\n", filename);
  
  status = lstat(filename, &file_stat);
  if (must_exist && status == -1) {
    printf("File %s does not exist.\n", filename);
    return -1;
  }
  
  if (status == 0 && !S_ISREG(file_stat.st_mode)) {
    printf("File %s must be a regular file.\n", filename);
    return -1;
  }
  
  *fp = fopen(filename, mode);
  if (*fp == NULL) {
    printf("Unable to open file %s\n", filename);
    return -1;
  }
  rewind(*fp);

  printf("File %s opened successfully...\n", filename);
  return 0;
}

/**
  Computes the Burrows-Wheeler transform for the input string provided.
  \param input - String to be transformed.
  \param size - Size of the string to be transformed.
  \param output - String where the resulting transformation will be returned.
  \param index - Pointer to an integer where the output index of the BWT will
  be returned.
*/
void bw_c(char input[], int size, char output[], int *index)
{
  char table[SIZE][SIZE+1];
  int sorted_indices[SIZE], i;

  set_table(table, input, size);
  set_indices(sorted_indices);  
  sort_table(table, 0, size-1, sorted_indices);
  
  for (i = 0; i < size; ++i) {
    if (sorted_indices[i] == 0)
      *index = i;
    output[i] = table[sorted_indices[i]][size-1];
  }
  output[i] = '\0';
}

/**
  Sets the table used to do BWT.
  \param table - 2D array of char that represents the table.
  \param input - Input string to be encoded.
  \param len - actual lenght of the string. The string could have length up to
  SIZE, but it could be shorter than that.
*/
void set_table(char table[][SIZE+1], char input[SIZE+1], int len)
{
  int i, j;
  strcpy(table[0], input);
  for (i = 1; i < len; ++i) {
    table[i][0] = table[i-1][len-1];
    /*TODO: there must be a way to do this using memcpy; which should be
    faster.*/
    for (j = 1; j < len; ++j)
      table[i][j] = table[i-1][j-1];
    table[i][j] = '\0';
  }
}

/**
  Sets the values of the elements in the indices array equal to the index of
  the item.  Note that this function assumes that the indices array has the
  globally defined size.
  \param indices - Pointer to an array of integers.
*/
void set_indices(int *indices)
{
  int i;
  if (indices == NULL)
    return;
  for (i = 0; i < SIZE; ++i)
    indices[i] = i;
}

/**
  Sorts the rows in the table in lexicographical order using the merge sort
  algorithm.
  \param table - Table whose rows will be sorted.
  \param start - Integer representing index of first row that is being sorted.
  \param end - Integer representing the index of the last row that is being
  sorted.
  \param indices - Array of integers representing the order of the rows after 
  they are sorted.
*/
void sort_table(char table[][SIZE+1], int start, int end, int indices[SIZE])
{
  int temp_index, temp_indices[SIZE];
  int middle, right_count, left_count;
  int i, j, k;
  
  /*Only one element or no elements to sort.*/
  if (end <= start)
    return;
  
  /*Two elements to sort.*/
  if ((end - start) == 1) {
    if (strcmp(table[start], table[end]) > 0) {
      temp_index = indices[start];
      indices[start] = indices[end];
      indices[end] = temp_index;
    }
    return;
  }
  
  middle = (start + end) / 2;
  sort_table(table, start, middle, indices);
  sort_table(table, middle + 1, end, indices);
    
  left_count = middle - start + 1;
  right_count = end - middle;
  i = start;
  j = middle + 1;
  k = 0;  
  while (left_count > 0 && right_count > 0) {
    if (strcmp(table[indices[i]], table[indices[j]]) < 0) {
      temp_indices[k] = indices[i];
      --left_count;
      ++i;
    } else {
      temp_indices[k] = indices[j];
      --right_count;
      ++j;
    }
    ++k;
  }
  
  while (left_count > 0) {
    temp_indices[k] = indices[i];
    --left_count;
    ++i;
    ++k;
  }
  
  while (right_count > 0) {
    temp_indices[k] = indices[j];
    --right_count;
    ++j;
    ++k;
  }
  
  k = 0;
  for (i = start; i <= end; ++i) {
    indices[i] = temp_indices[k];
    ++k;
  }
}

/**
  move-to-front implementation.
*/
int mtfencode(unsigned char* dst, unsigned char* src, int length)
{
  int i, j;
  unsigned char table[256];
  for(i = 0; i < 256; i++)
    table[i] = i;
  for(i = 0; i < length; i++){
    for(j = 0; j < 256; j++)
      if(src[i] == table[j])
        break;
    if(j >= 256)
      return -1;
    dst[i] = j;
    for( ; j > 0; j--)
      table[j] = table[j-1];
    table[0] = src[i];
  }
  dst[i] = '\0';
}

void swap(Node a, Node b)
{
  Node t;
  t.value = a.value; t.prob = a.prob; 
  a.value = b.value; a.prob = b.prob; 
  b.value = t.value; b.prob = t.prob;
}

void sort(Node arr[], int beg, int end)
{
  if (end > beg + 1)
  {
    Node piv = arr[beg];
    int l = beg + 1, r = end;
    while (l < r)
    {
      if (arr[l].prob <= piv.prob)
        l++;
      else
        swap(arr[l], arr[--r]);
    }
    swap(arr[--l], arr[beg]);
    sort(arr, beg, l);
    sort(arr, r, end);
  }
}

int huffencode(unsigned char* dst, unsigned char* src, int length){
  int i, j;
  Node table[256], *root, *tree = malloc(sizeof(Node));
  for(i = 0; i < 256; i++){
    table[i].value = i;
    table[i].prob = 0;
  }
  for(i = 0; i < length; i++)
    (table[src[i]].prob)++;
  sort(table, 0, 256);
  for(i = 0; i < 256-1; i++){
    Node *l, *r;
    if(table[i].value != NaB){
      tree->value = table[i].value;
      tree->prob = table[i].prob;
      l = tree;
      tree->next = malloc(sizeof(Node));
      tree = (Node*)tree->next;
    }
    else
      l = (Node*)table[i].next;
    if(table[i+1].value != NaB){
      tree->value = table[i+1].value;
      tree->prob = table[i+1].prob;
      r = tree;
      tree->next = malloc(sizeof(Node));
      tree = (Node*)tree->next;
    }
    else
      l = (Node*)table[i+1].next;
    tree->value = NaB;
    tree->prob = l->prob+r->prob;
    tree->right = (void*)r;
    tree->left = (void*)l;
    if(i < 254){
      tree->next = malloc(sizeof(Node));
      table[i+1].value = NaB;
      table[i+1].prob = l->prob+r->prob;
      table[i+1].next = (void*)tree;
      tree = (Node*)tree->next;
    }
    else
      root = tree;
  }

  /*
  printTree(root);
  dst[i] = '\0';
  */
}
